DROPS

Document

DOI: 10.4230/LIPIcs.AofA.2022.2

On the Independence Number of Random Trees via Tricolourations

Authors: Etienne Bellin

Published in: LIPIcs, Volume 225, 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)

Abstract

We are interested in the independence number of large random simply generated trees and related parameters, such as their matching number or the kernel dimension of their adjacency matrix. We express these quantities using a canonical tricolouration, which is a way to colour the vertices of a tree with three colours. As an application we obtain limit theorems in L^p for the renormalised independence number in large simply generated trees (including large size-conditioned Bienaymé-Galton-Watson trees).

Cite as

Etienne Bellin. On the Independence Number of Random Trees via Tricolourations. In 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 225, pp. 2:1-2:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bellin:LIPIcs.AofA.2022.2,
  author =	{Bellin, Etienne},
  title =	{{On the Independence Number of Random Trees via Tricolourations}},
  booktitle =	{33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)},
  pages =	{2:1--2:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-230-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{225},
  editor =	{Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2022.2},
  URN =		{urn:nbn:de:0030-drops-160886},
  doi =		{10.4230/LIPIcs.AofA.2022.2},
  annote =	{Keywords: Independence number, simply generated tree, Galton-Watson tree, tricolouration}
}

Search Results

Documents authored by Bellin, Etienne

On the Independence Number of Random Trees via Tricolourations

Abstract

Cite as

Thanks for your feedback!

Could not send message